package num56I;

/**
 * @author : DuJiabao
 * @Date : 2021/1/22 19:18
 * @Project : sword-finger-offer
 * @File : null.java
 * @Desc :一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
 * https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/
 */

/**
 * 这题真的很巧妙。
 */
public class Solution {
    public int[] singleNumbers(int[] nums) {
        int ret = 0;// 0异或任何值都等于它自身。自己异或自己，等于0
        // 最终留下两个不相等的值的异或值
        for (int num : nums) {
            ret ^= num;
        }
//        现在寻找两个值的第一个不相同位,即ret为1的第一个位。进而将两个数分成两组
        int h = 1;
        int a = 0;
        int b = 0;
        while ((h & ret) == 0) {
            h <<= 1;  // 寻找第一个不相等的位
        }
//      将数字分为两组，相同的数字肯定会分成一组而自己消掉。不相同的数字则会各为一组，即数字。
        for (int num : nums) {
            if ((num & h) == 0) {
                a ^= num;
            } else {
                b ^= num;
            }
        }
        return new int[]{a, b};
    }
}
